package cn.chencq.collection.list;


public class MyLinkedList {

	private Node first;
	private Node last;

	private int size;

	public int size() {
		return size;
	}

	public void add(Object obj) {
		Node n = new Node();
		if (first == null) {
			n.setPrevious(null);
			n.setObj(obj);
			n.setNext(null);

			first = n;
			last = n;
		} else {
			n.setPrevious(last);
			n.setObj(obj);
			n.setNext(null);

			last.setNext(n);

			last = n;
		}
		size++;
	}

	public Object add(int index, Object obj) {
		Node oldNode = node(index);
		Node preNode = oldNode.getPrevious();

		Node newNode = new Node();
		newNode.setNext(oldNode);
		newNode.setObj(obj);
		newNode.setPrevious(preNode);

		if (preNode != null) {
			preNode.setNext(newNode);
		} else {
			first = newNode;
		}
		oldNode.setPrevious(newNode);

		size++;

		return newNode;
	}
	public Object set(int index, Object obj) {
		Node n = node(index);
		Object old = n.getObj();
		n.setObj(obj);
		return n;
	}

	public boolean remove(Object obj) {
		if (obj == null) {
			for (int i = 0; i < size(); i++) {
				if (get(i) == null) {
					remove(i);
					return true;
				}
			}
		} else {
			for (int i = 0; i < size(); i++) {
				if (get(i).equals(obj)) {
					remove(i);
					return true;
				}
			}
		}
		return false;
	}

	public boolean remove(int index) {
		Node node = node(index);
		return removeNode(node);
	}

	public boolean removeNode(Node node) {
		if (node == first) {// ??????????????
			Node next = first.getNext();
			next.setPrevious(null);

			node = null;

			first = next;
			size--;
			return true;
		} else if (node == last) {
			Node preNode = last.getPrevious();
			preNode.setNext(null);

			node = null;

			size--;
			return true;
		} else {
			Node next = node.getNext();
			Node preNode = node.getPrevious();

			preNode.setNext(next);

			next.setPrevious(preNode);

			size--;
			return true;
		}
	}

	public Object get(int index) {
		Node n = node(index);
		return n.getObj();
	}

	private Node node(int index) {
		rangeCheck(index);

		Node tmp = null;
		if (first != null) {
			if (index < (size >> 1)) {
				tmp = first;
				for (int i = 0; i < index; i++) {
					tmp = tmp.getNext();
				}
			} else {
				tmp = last;
				for (int i = size - 1; i > index; i--) {
					tmp = tmp.getPrevious();
				}
			}
		}
		return tmp;
	}

	private void rangeCheck(int index) {
		if (index < 0 || index >= size)
			throw new IndexOutOfBoundsException("Index: " + index + ", Size: "
					+ size);
	}

	public static void main(String[] args) {
		MyLinkedList list = new MyLinkedList();
		list.add("aaa");
		list.add("bbb");
		list.add("ccc");
		// System.out.println(list.get(8));

		System.out.println("????????:" + list.size());
		System.out.println("????????????:" + list.get(1));
		System.out.println("????2?????:" + list.remove(1));
		System.out.println("????????????:" + list.size());
		list.set(1, "ddd");
		System.out.println("????????????????:" + list.get(1));

		list.add("eee");
		list.add("ddd");
		list.add("ggg");
		list.add("hhh");
		for (int i = 0; i < list.size(); i++) {
			System.out.print(list.get(i) + ",");
		}
		System.out.println("------------------");

		list.add(2, "kkk");
		list.add(0, "111");
		for (int i = 0; i < list.size(); i++) {
			System.out.print(list.get(i) + ",");
		}
		System.out.println("------------------");

		list.remove("ddd");
		for (int i = 0; i < list.size(); i++) {
			System.out.print(list.get(i) + ",");
		}
	}
}
